#include <vector>
#include <stack>

using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
};

class Solution
{
public:
    bool findPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        if (root == nullptr)
        {
            return false;
        }
        path.push(root);
        if (root == x || findPath(root->left, x, path) || findPath(root->right, x, path))
        {
            return true;
        }
        else
        {
            path.pop();
            return false;
        }
    }

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        stack<TreeNode *> pPath, qPath;
        findPath(root, p, pPath);
        findPath(root, q, qPath);

        while (pPath.size() < qPath.size())
        {
            qPath.pop();
        }

        while (qPath.size() < pPath.size())
        {
            pPath.pop();
        }

        while (qPath.top() != pPath.top())
        {
            qPath.pop();
            pPath.pop();
        }
        return pPath.top();
    }
};

